package leetcodev1.链表;

import java.util.HashSet;
import java.util.Set;

public class LeetCode160 {
    //两个链表中的相同元素
    //没有则返回null
    //题目保证无环
    //1.第一个链表搞一个hash表 遍历第二个链表 时间复杂度o(m+n) 空间复杂度o(m) 链表无法比较大小
    //2.双重循环 时间复杂度o(m*n) 空间复杂度0
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> dict = new HashSet<>();
        ListNode indexA = headA, indexB = headB;
        while (indexA != null) {
            dict.add(indexA);
            indexA = indexA.next;
        }

        while (indexB != null) {
            if (dict.contains(indexB)) {
                return indexB;
            }
            indexB = indexB.next;
        }

        return null;
    }
}

class Answer160 {
    //1.hash算法同上面
    //2.双指针 算法及其巧妙!!!
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            //当前队列如果为空 则移动到另一个队列的头节点
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;//两种情况pA==pB pA==null
    }
}
